package targetToOffer.nintehDay;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Godc
 * @description
 */
public class MaxSlidingWindow {
    public static void main(String[] args) {
        MaxSlidingWindowSolution s = new MaxSlidingWindowSolution();
        int[] ints = s.maxSlidingWindow1(new int[]{1, 3, 1 , 2 , 0 , 5}, 3);
        System.out.println(Arrays.toString(ints));
    }
}
class MaxSlidingWindowSolution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        LinkedList<Integer> stack = new LinkedList<>();
        if(nums.length==0) return new int[0];
        int[] res = new int[nums.length-k+1];
        int x = 0;
        int max = Integer.MIN_VALUE;
        for(int i = 0;i<=nums.length-k;i++){
            for(int j = i;j<=k+i-1;j++){
                if(nums[j]>max) max= nums[j];
            }
            res[x++] = max;
            max = Integer.MIN_VALUE;
        }
        return res;
    }
    public int[] maxSlidingWindow1(int[] nums, int k) {
        if(nums.length==0) return new int[0];
        int[] res = new int[nums.length-k+1];
        Deque<Integer> queue = new ArrayDeque<>();
        int x = 0;
        for(int i = 0;i<k;i++){
            while(!queue.isEmpty()&&queue.peekLast()<nums[i])
                queue.pollLast();
            queue.addLast(nums[i]);
        }
        res[x++] = queue.peekFirst();
        for(int i = k;i<nums.length;i++){
            if(nums[i-k]==queue.peekLast()) queue.pollFirst();
            while(!queue.isEmpty()&&queue.peekLast()<nums[i])
                queue.pollLast();
            queue.addLast(nums[i]);
            res[x++] = queue.peekFirst();
        }
        return res;
    }
}